#include<bits/stdc++.h>
using namespace std;
int Stack[400000];
void hexTooct(string str, int length){
    int top = -1;
    for (int i = length-1; i >= 0; i-=3)
    {
        int sum = 0;
        for (int j = 0; j < 3 && i-j >= 0; j++)
        {
            int temp = str[i-j] >= '0' && str[i-j] <= '9' ? str[i-j] - '0':str[i-j] - 'A' +10;
            sum += temp << (4*j);
        }
        Stack[++top] = sum;   
    }
    while (Stack[top] == 0)
    {
        top--;
    }
    printf("%o",Stack[top--]);
    while (top >= 0)
    {
        printf("%04o",Stack[top--]);
    }
    cout << endl;
}
int main(){
    int n;
    string *str;    //字符串指针
    cin >> n;
    str = new string[n];    //字符串指针指向字符串数组
    for (int i = 0; i < n; i++)
    {
        cin >> str[i];
    }
    for (int i = 0; i < n; i++)
    {
        hexTooct(str[i],str[i].size());
    }
    return 0;
}